import { Compare, defaultCompare } from "./utils";

/**最小堆 */
export class MiniHeap {

    heap: number[];
    compareFn: Function;
    constructor() {
        this.heap = [];
        this.compareFn = defaultCompare;
    }

    getLeftIndex(index) {//左侧子结点位置
        return 2 * index + 1;
    }

    getRightIndex(index) {//右侧子结点位置
        return 2 * index + 2;
    }

    getParentIndex(index) {//父结点位置
        if (index == 0) {
            return undefined;
        }
        return Math.floor((index - 1) / 2);
    }

    /**向堆中插入一个新的值*/
    insert(value) {
        if (value != null) {
            this.heap.push(value);
            this.siftUp(this.heap.length - 1);
            return true;
        }
        return false;
    }

    /**移除最小值，并返回这个值 */
    extract() {
        if (this.isEmpty()) {
            return undefined;
        }
        if (this.size() == 1) {
            return this.heap.shift();
        }
        const removeValue = this.heap.shift();
        this.siftDown(0);
        return removeValue;
    }

    /**返回最小值，且不会移除这个值 */
    findMinimum() {
        return this.isEmpty() ? undefined : this.heap[0];
    }

    /**上移操作 up head、percolate up、bubble up、heapify up或cascade up*/
    siftUp(index: number) {
        let parent = this.getParentIndex(index);
        while (index > 0 && this.compareFn(this.heap[parent], this.heap[index]) == Compare.BIGGER_THAN) {
            this.swap(parent, index);
            index = parent;
            parent = this.getParentIndex(index);
        }
    }
    /**下移操作（堆化） */
    siftDown(index: number) {
        let element = index;
        const left = this.getLeftIndex(index);
        const right = this.getRightIndex(index);
        const size = this.size();

        if (left < size && this.compareFn(this.heap[element], this.heap[left]) === Compare.BIGGER_THAN) {
            element = left;
        }

        if (right < size && this.compareFn(this.heap[element], this.heap[right]) === Compare.BIGGER_THAN) {
            element = right;
        }

        if (index !== element) {
            this.swap(index, element);
            this.siftDown(element);
        }
    }

    heapify(array: number[]) {
        if (array) {
            this.heap = array;
        }

        const maxIndex = Math.floor(this.size() / 2) - 1;

        for (let i = 0; i <= maxIndex; i++) {
            this.siftDown(i);
        }

        return this.heap;
    }

    swap(a: number, b: number) {
        const temp = this.heap[a];
        this.heap[a] = this.heap[b];
        this.heap[b] = temp;
    }

    size() {
        return this.heap.length;
    }

    isEmpty() {
        return this.size() === 0;
    }

    findMininum() {
        return this.isEmpty() ? undefined : this.heap[0];
    }

}


